package com.xk._03真题骗._02链表;

import com.xk._03真题骗._00bean.ListNode;

/*
 * @description: https://leetcode.cn/problems/palindrome-linked-list/
 * @author: xu
 * @date: 2022/10/27 21:00
 */
public class _234回文链表 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
        //head.next.next.next.next = new ListNode(1);
        boolean palindrome = new _234回文链表().isPalindrome(head);
        System.out.println(palindrome);
    }

    public boolean isPalindrome(ListNode head) {
        // 只有一个节点的情况
        if (head.next == null) return true;
        // 只有两个节点的情况
        if (head.next.next == null) return head.val == head.next.val;

        // 找到中间节点
        ListNode mid = middleNode(head);
        // 翻转右半部分（中间节点的右半部分）
        ListNode rHead = reverseList(mid.next);
        ListNode lHead = head;
        boolean result = true;
        while (rHead != null) {
            if (lHead.val != rHead.val) result = false;
            rHead = rHead.next;
            lHead = lHead.next;
        }
        return result;
    }

    /*
     * 找到中间节点（右半部分链表头节点的前一个节点）
     * 比如 1->2->3->2->1 中的3是中间节点
     * 比如 1->2->4->3->2->1 中的4是中间节点
     */
    private ListNode middleNode(ListNode head) {
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /*
     * 翻转链表
     * @param head 原链表的头结点
     * @return 翻转之后链表的头结点
     * 1->2->3  ==> 3->2->1
     */
    private ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}
